package com.stock;

/**
 * 快速排序
 * Created by zhangfeng on 16/10/27.
 */
public class QuickSort {

    private static boolean isEmpty(int[] n){
        return n == null || n.length == 0;
    }

    /**
     * 快速排序算法思想--挖坑填数方法
     * @param
     */
    public static void quickSort(int[] n){
        if (isEmpty(n))
            return;
        quickSort(n,0,n.length -1);
    }

    public static void quickSort(int[] n,int l,int h){
        if (isEmpty(n))
            return;
        if (l < h){
            int pivot = partion(n,l,h);
            quickSort(n,l,pivot - 1);
            quickSort(n,pivot + 1,h);
        }
    }

    public static int partion(int[] n,int start,int end){
        int tmp = n[start];
        while(start < end){
            while (n[end] >= tmp && start < end)
                end--;
            if (start < end){
                n[start++] = n[end];
            }
            while(n[start] <tmp && start < end)
                start++;
            if (start < end){
                n[end--] = n[start];
            }
        }
        n[start] = tmp;
        return start;
    }

    public static void main(String[] args){
        int[] n = new int[]{37,40,38,42,461,5,7,9,12,8,5,8,6,2,3,1,4,13};
        quickSort(n);
        for (int i = 0  ; i < n.length ; i ++) {
            System.out.println(n[i]);
        }
    }
}
